#
# @lc app=leetcode.cn id=69 lang=python3
#
# [69] x 的平方根 
#

# @lc code=start
class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 2, x//2

        if x >= 4:
            while left <= right:
                mid = left + (right - left) // 2
                if mid*mid < x:
                    left = mid + 1
                elif mid*mid > x:
                    right = mid - 1
                else:
                    return mid
            return right
        elif x == 0:
            return 0
        else: 
            return 1
# @lc code=end

